/*
 * @lc app=leetcode.cn id=116 lang=typescript
 *
 * [116] 填充每个节点的下一个右侧节点指针
 */

// @lc code=start
/**
 * Definition for Node.
 * class Node {
 *     val: number
 *     left: Node | null
 *     right: Node | null
 *     next: Node | null
 *     constructor(val?: number, left?: Node, right?: Node, next?: Node) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

//  思路：递归
//  要注意连接不同父节点的节点
//  参考：https://labuladong.github.io/algo/2/19/22/

//  复杂度：O(n) O(1)

function connectTwoNode(node1: Node | null, node2: Node | null) {
    if (!node1 || !node2) return null
    node1.next = node2
    // 连接相同父节点的两个子节点
    connectTwoNode(node1.left, node1.right)
    connectTwoNode(node2.left, node2.right)
    // 连接跨越父节点的两个子节点
    connectTwoNode(node1.right, node2.left)
}

function connect(root: Node | null): Node | null {
    if (!root) return null
    connectTwoNode(root.left, root.right)
    return root
};


// @lc code=end


class Node {
    val: number
    left: Node | null
    right: Node | null
    next: Node | null
    constructor(val?: number, left?: Node, right?: Node, next?: Node) {
        this.val = (val === undefined ? 0 : val)
        this.left = (left === undefined ? null : left)
        this.right = (right === undefined ? null : right)
        this.next = (next === undefined ? null : next)
    }
    static PrintTree(root: Node | null): string {
        let str = ''
        while (root) {
            str += root.val
            str += '->'
            let next = root.next
            while (next) {
                str += next.val
                str += '->'
                next = next.next
            }
            root = root.left
        }
        return str
    }
}

export { }

const root = new Node(1, new Node(2, new Node(4), new Node(5)), new Node(3, new Node(6), new Node(7)))
console.log(Node.PrintTree(connect(root)))

